The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


9.9.3 Choosing the Plaintexts to Request

From U′, V′, it is possible to generate a set of about 232 XOR difference values that we can expect to see result from the changed subkeys when they’re used in the F function in the first round. We thus do the following:

1.  Request the encryption of some fixed 128-bit block A, B, C, D under key K.
2.  For each of the 232 different 64-bit XOR difference values, Xi, Yi, we might expect from U′, V′, request the encryption of 128-bit block (A, B, CXi, DYi).
3.  Consider only those ciphertexts from the second step that lead to the same right half of ciphertext as the encryption under K in the first step. The goal is to determine the output XOR from the first round’s F function when the input is A, B, under the two keys. (The only difference in the output is caused by the difference in round subkeys.) Note that we expect to have about one false positive occur; we simply run the attack on both potential right pairs; the wrong pair will not allow the attacker to find any S-box offsetting differences.

9.9.4 Extracting the Key Material

At this point, we know the single XOR difference from the F function. We can now learn the S-boxes in the g function. To do this, we replace the high-order byte of A in the right pair with 256 different values. Thus, we request the encryption of Aj, B, C, D under K*. This causes one of 256 possible XOR differences in the g function output. We expect to have to try about 512 requests with different XOR difference values Xi, Yi, where these values are derived from the Xi, Yi values that generated the original right pair based on the possible XOR differences in g. We thus request 512 plaintexts of the form Aj, B, CXi, DYi) to be encrypted under K*. One of these we expect to be a right pair, which we can recognize, again, by the fact that the right half of the ciphertext is the same for Aj, B, C, D encrypted under K, and for Aj, B, CXi, DYi encrypted under K*.

After carrying this out for each of the Aj, we have good information about the XOR differences being generated from g by the changes between A and Aj as input. In particular, we will note the 14 cases where we probably got 8-bit Hamming weights in the output XOR difference of g. This information should be enough to brute-force this S-box, s3. That is, we try all 232 possible S-boxes for s3, and expect one to be the best fit for our data.

We repeat the attack for each of the other bytes in A, so that we recover all four S-boxes in g. When we know these S-boxes, this means we know S. Note that at the beginning of the attack, we already know 20 of the 32 key bytes used. More importantly, due to the structure of the RS matrix used to derive S from the raw key bytes, we know all but three bytes used to derive each 4-byte “row” of values in S. This allows us to guess and check the remaining key bytes three bytes at a time, thus recovering the entire key.

9.10 Side-Channel Cryptanalysis and Fault Analysis

Resistance to these attacks was not part of the AES criteria, and hence not a major concern in this design. However, we do have these comments to make on the design.

Side-channel cryptanalysis [KSWH98b] uses information about the cipher in addition to the plaintext or ciphertext. Examples include timing [Koc96], power consumption (including differential power analysis [Koc98a]), NMR scanning, and electronic emanations.5 With many algorithms it is possible to reconstruct the key from these side channels. While total resistance to side-channel cryptanalysis is probably impossible, we note that Twofish executes in constant time on most processors.


5The NSA refers to this particular side channel as "TEMPEST."

Fault analysis [BDL97, BS97] can be used to successfully cryptanalyze this cipher. Again, we believe that total resistance to fault analysis is an impossible design constraint for a cipher. The resistance to fault analysis of any block cipher can be improved using classical tamper-resistance and fault-tolerance techniques (although see [AK96]).

In most cases, Twofish seems to be inherently resistant to timing analysis. However, it is worth noting that in certain special cases, implementers may need to take extra care to avoid the possibility of timing attacks. On platforms with extremely limited memory resources, it is natural to compute the multiplies over GF(28) on the fly without the aid of additional tables by using a shift-register-based approach. If this approach is to be followed, beware: timing attacks may be possible. The obvious way to clock a shift register in software is to shift it and then XOR in the feedback polynomial if the bit that shifted out was a one—but this algorithm does not execute in constant time, because the XOR operation is performed only if a certain data bit is set. Thus, this implementation pattern should be avoided. A better approach would be to XOR in either zero or the feedback polynomial, depending on the value of the bit just shifted out, thereby guaranteeing constant-time execution and resistance to timing analysis. This is probably only of concern to smart cards and other computing platforms without much memory.

9.11 Attacking Simplified Twofish

9.11.1 Twofish with Known S-boxes

As discussed above, our differential attack on Twofish with fixed S-boxes works for 6-round Twofish, and requires only 267 effort. A 7-round differential attack requires 2131 effort.

Additionally, much of Twofish’s related-key attack resistance comes from the derivation of the S-boxes, so a related-key attack is much easier against a known S-box variant.

9.11.2 Twofish without Round Subkeys

We attack a Twofish variant without any subkeys, thus whose whole key material is in the key-dependent S-boxes. The attack requires about 233 chosen plaintexts; it breaks the Twofish variant with about 236 effort, even when the cipher has a 128-bit key. (Note that this is the amount of key material used to define the S-boxes in normal Twofish with a 256-bit key.)

It is obvious that a Twofish variant with fixed S-boxes and no subkeys would be insecure—there would be no key material injected. We develop a slide attack on Twofish with any number of rounds, and a 128-bit key. (The Twofish key would be 256 bits, but since we never use more than 128 bits of key in the key-dependent S-boxes, the effective key size is 128 bits.)

Note that this attack would not work if we used round subkeys that were simply counter values, as would happen if we used the identity permutation for all the key-scheduling S-boxes. We are not currently aware of any attack on such a Twofish variant.

Overview of the Attack. In a slide attack, we attempt to find a pair of plaintexts, (P, P*), such that P* has the same value as the intermediate value after one or more rounds of encrypting P. If we can find and expose this value, we gain direct access to the results of a single round of the cipher; we then attack that single round to recover the key.

Our attack has two parts:

1.  We must first find a pair of plaintexts, (P, P*), such that P* is the result of encrypting P with one round.
2.  We use this pair to derive four relations on g and thus determine the specific S-boxes used in g. This yields the effective key of the cipher.

Finding Our Related Pair of Texts. Twofish is a Feistel cipher, operating on two 64-bit halves in each block. We use the representation where the left half of the block is the input to the Feistel function, and the halves are swapped after each round. Let (L0, R0) represent a given pair of 64-bit halves input into the cipher, and let (LN, RN) represent the resulting ciphertext. To mount this attack, we need to find some (L0, R0, L1) such that L1 is the value of the left half of the block after the first round. To test whether we have such a pair, we can try encrypting (L0, R0) and (L1, L0). When we have a triple with the desired properties, we get (LN, RN) from the first encryption, and (LN+1 LN) from the second encryption.

We use a trick by Biham [Bih94] to get such a pair of plaintexts with only 233 chosen plaintexts: we choose a fixed L0, and encrypt it with 232 randomly selected R0 values as (L0, R0). We then encrypt the same L0 with 232 random R1, values, as, (R1, L0). By the birthday paradox, we expect to see one pair of values for which R1 = R0F(L0). To find this pair, we sort the ciphertexts from the first batch of encryptions on their left halves, and the ciphertexts from the second batch of encryptions on their right halves. When we find a match, the probability is good that we have a pair with the desired property.


Previous Table of Contents Next